/**
 * 
 */
package tree.passed;

import java.util.HashMap;
import java.util.Map;

/**
 * @author michaelyi
 *
 */
public class TreeSerialization {

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	Construct Binary Tree from Inorder and Postorder Traversal
	
	Given inorder and postorder traversal of a tree, construct the binary tree.

	Note:
	You may assume that duplicates do not exist in the tree.
	 */
	public TreeNode buildTreeIPost(int[] inorder, int[] postorder) {
		Map<Integer, Integer> reverseMap = this.valueToIndexMap(inorder);
		return buildTreeIPostHelper(postorder, postorder.length - 1, inorder,
				inorder.length - 1, inorder.length, reverseMap);
	}

	public TreeNode buildTreeIPostHelper(int[] postOrder, int postIndex,
			int[] inOrder, int inIndex, int treeSize,
			Map<Integer, Integer> reverseMap) {
		if (treeSize == 0)
			return null;

		int value = postOrder[postIndex];
		int index = reverseMap.get(value);
		int rightSize = inIndex - index;
		int leftSize = treeSize - rightSize - 1;
		TreeNode node = new TreeNode(value);
		node.right = buildTreeIPostHelper(postOrder, postIndex - 1, inOrder,
				inIndex, rightSize, reverseMap);
		node.left = buildTreeIPostHelper(postOrder, postIndex - rightSize - 1,
				inOrder, index - 1, leftSize, reverseMap);

		return node;
	}

	/**
	Construct Binary Tree from Preorder and Inorder Traversal
	
	Given preorder and inorder traversal of a tree, construct the binary tree.

	Note:
	You may assume that duplicates do not exist in the tree.
	 */
	public TreeNode buildTreeIPre(int[] preorder, int[] inorder) {
		Map<Integer, Integer> inorderRverseMap = valueToIndexMap(inorder);
		return buildTreeIPreHelper(preorder, 0, inorder, 0, preorder.length,
				inorderRverseMap);
	}

	public TreeNode buildTreeIPreHelper(int[] preorder, int preIndex,
			int[] inorder, int inStart, int treeSize,
			Map<Integer, Integer> valueToIndexMap) {
		if (treeSize == 0)
			return null;
		int value = preorder[preIndex];
		int inIndex = valueToIndexMap.get(value);
		int leftSize = inIndex - inStart;
		int rightSize = treeSize - leftSize - 1;
		TreeNode node = new TreeNode(value);
		node.left = buildTreeIPreHelper(preorder, preIndex + 1, inorder,
				inStart, leftSize, valueToIndexMap);
		// pitfall the priIndex of left tree is preIndex + leftSize  + 1 (not to forget 1)
		node.right = buildTreeIPreHelper(preorder, preIndex + leftSize + 1,
				inorder, inIndex + 1, rightSize, valueToIndexMap);

		return node;
	}

	public Map<Integer, Integer> valueToIndexMap(int[] arr) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		if (arr == null || arr.length == 0)
			return map;

		for (int i = 0; i < arr.length; i++) {
			map.put(arr[i], i);
		}

		return map;
	}

	public final static String SEPARATOR = "#";

	/**
	 * 
	 */
	public TreeSerialization() {
		// TODO Auto-generated constructor stub
	}

	public String serializeTree(tree.TreeNode<Character> root) {
		/*
		if (root == null) throw new Exception("NULL");
		
		String inOrder = inOrderTraverse(root);
		String preOrder = preOrderTraverse(root);
		StringBuilder strBuilder = new StringBuilder();
		strBuilder.append(inOrder).append(SEPARATOR).append(preOrder);
		return strBuilder.toString();
		*/
		return null;
	}

	tree.TreeNode<Character> deserializeTree(String treeString)
			throws Exception {

		if (treeString == null)
			throw new Exception("NULL");
		if (treeString.equals(""))
			throw new Exception("Empty");

		String[] treeStrs = treeString.split(SEPARATOR);
		if (treeStrs.length != 2)
			throw new Exception("Wrong format of treeString");

		String inOrder = treeStrs[0];
		if (inOrder.equals(""))
			throw new Exception("Empty Inorder");

		String preOrder = treeStrs[1];
		if (preOrder.equals(""))
			throw new Exception("Empty preorder");

		if (inOrder.length() != preOrder.length())
			throw new Exception("Wrong size of preorder and inorder");

		Map<Character, Integer> inOrderMap = mapValue2Index(inOrder);

		return buildInPreOrderTree(preOrder, 0, inOrder, 0, inOrder.length(),
				0, inOrderMap);
	}

	/**
	 * To build a map to find the inorder index by value in constant time
	 * @param inorder, in-order string
	 * @return a map match the char value with the index in the string
	 */
	private Map<Character, Integer> mapValue2Index(String inorder) {
		assert (inorder != null && !inorder.equals(""));

		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < inorder.length(); i++) {
			map.put(inorder.charAt(i), i);
		}

		return map;
	}

	/**
	 * 
	 * @param preOrder, pre-order string
	 * @param preIndex, pre-order stirng current index
	 * @param inOrder, in-order string
	 * @param inIndex, in-order string current index
	 * @param size, the size of current tree
	 * @param offset, the offset of current index in in-order string (for right child tree) 
	 * @param inorderMap. a map for value and index of in-order tree
	 * @return root node
	 */
	tree.TreeNode<Character> buildInPreOrderTree(String preOrder, int preIndex,
			String inOrder, int inIndex, int size, int offset,
			Map<Character, Integer> inorderMap) {
		assert (preOrder != null && inOrder != null);
		assert (preOrder.length() == inOrder.length());
		assert (size >= 0);

		if (size == 0)
			return null;

		char value = preOrder.charAt(preIndex);
		int index = inorderMap.get(value) - offset;
		tree.TreeNode<Character> root = new tree.TreeNode<Character>(value);
		root.left = buildInPreOrderTree(preOrder, preIndex + 1, inOrder,
				inIndex, index, offset, inorderMap);
		root.right = buildInPreOrderTree(preOrder, preIndex + index + 1,
				inOrder, inIndex + index + 1, size - index - 1, offset + index
						+ 1, inorderMap);
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeSerialization rs = new TreeSerialization();
		int[] preorder = new int[] { 1, 2 };
		int[] inorder = new int[] { 1, 2 };
		rs.buildTreeIPre(preorder, inorder);
	}

}
